package com.sourcestruct.linearlist;

import lombok.ToString;

/**
 * @author: ZhouBert
 * @date: 2019/6/9
 * @description: 用数组实现循环队列
 * 循环链表不使用扩容，而采用动态指针 head tail
 */
@ToString
public class CircularArrayQueue<T> {

	/**
	 * 存储数据
	 */
	private T[] data;
	/**
	 * 实际大小
	 */
	private int size;
	/**
	 * 头指针
	 */
	private int head;
	/**
	 * 结尾指针
	 */
	private int tail;

	/**
	 * constructor to create capacity
	 *
	 * @param capacity
	 */
	public CircularArrayQueue(int capacity) {
		data = (T[]) new Object[capacity];
		head = 0;
		tail = -1;
		size = 0;
	}

	/**
	 * 入队
	 */
	public void queue(T obj) {
		///1.大小超出
		if (size == data.length) {
			throw new IllegalArgumentException("队列已满！");
		}
		///2.需要将索引归零
		if (tail == data.length - 1) {
			tail = 0;
			data[0] = obj;
		}
		///3.直接添加到后面
		else {
			data[++tail]=obj;
		}
		size++;
	}


	public T dequeue(){
		///1.空队列异常
		if (size==0){
			throw new IllegalArgumentException("队列为空！");
		}
		size--;
		///2.头结点循环缩进
		if (head==data.length-1){
			head=0;
			return data[data.length-1];
		}
		///3.头结点简单缩进
		else{
			return data[head++];
		}

	}

	public static void main(String[] args) {
		CircularArrayQueue queue = new CircularArrayQueue(4);
		queue.queue(1);
		queue.queue(2);
		queue.queue(20);
		System.out.println(queue);
		System.out.println(queue.dequeue());
		System.out.println(queue);
		System.out.println(queue.dequeue());
		System.out.println(queue);
		System.out.println(queue.dequeue());
		System.out.println(queue);
		queue.queue(10);
		System.out.println(queue);
		queue.queue(11);
		System.out.println(queue);
	}
}
